package com.LeetCode.String;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * KMP字符串匹配算法
 */
public class KMP {

    /**
     * dp[1]['a'] = 0 表示 状态 1 遇到 'a' 字符之后应该转移到状态 '0'
     * */
    private int[][] dp;//确定状态自动机 -- 动态规划

    private String pat;//模式串




    /**
     * 查找 haystack 中 needle 第一次出现的字符下标
     */
    public int strStr2(String haystack, String needle) {
        if(needle.equals(""))
            return 0;
        if(haystack.equals(""))
            return -1;

        int n = haystack.length();
        int m = needle.length();
        //构造状态转移矩阵
        dp = new int[m][256];
        int x = 0;
        dp[0][needle.charAt(0)] = 1;
        for(int i = 1; i<m; i++){
            for(int j = 0; j<256; j++){
                dp[i][j] = dp[x][j];
            }
            dp[i][needle.charAt(i)] = i + 1;
            x = dp[x][needle.charAt(i)];
        }

        int stat = 0;
        for(int i = 0; i<n; i++){
            stat = dp[stat][haystack.charAt(i)];
            if(stat == m){
                return i - m + 1;
            }
        }
        return -1;
    }

    public int strStr3(String haystack, String needle) {
        if(needle.length() == 0)
            return 0;
        int i = 0, n = haystack.length();
        int j = 0, m = needle.length();
        int[] next = getNext(needle);
        while(i < n && j < m){
            if(j == -1 || needle.charAt(j) == haystack.charAt(i)){
                i++;
                j++;
            }else{
                j = next[j];
            }
        }
        return j == n ? i-j : -1;
    }


    public int[] getNext(String pat){
        char[] chars = pat.toCharArray();
        int n = chars.length;
        int[] next = new int[n+1];
        Arrays.fill(next, -1);
        int k = -1, j = 0;
        while(j < n-1){
            if( k == -1 || chars[k] == chars[j]){
                next[++j] = ++k;
            }else{
                k = next[k];
            }
        }
        return next;
    }

    public int charToInt(int idx, String s) {
        return (int)s.charAt(idx) - (int)'a';
    }


    public int strStr(String haystack, String needle) {
        int L = needle.length(),  n = haystack.length();
        if(L > n) return -1;

        int a = 26;

        long modules = (long)Math.pow(2,31);

        long h = 0, ref_h = 0;
        for(int i = 0; i < L; i++){
            h = (h * a + charToInt(i, haystack)) % modules;
            ref_h = (ref_h * a + charToInt(i, needle)) % modules;
        }

        if(h == ref_h)
            return 0;

        long aL = 1;
        for(int i = 1; i<=L; i++){
            aL = (aL * a) % modules;
        }

        for(int start = 1; start < n - L + 1; start++){
            h = (h * a - charToInt(start - 1, haystack) * aL
                    + charToInt(start + L - 1 ,haystack)) % modules;
            if( h == ref_h) return start;
        }
        return -1;
    }

    @Test
    public void test(){
        String a = "hello" , b = "ll";
        System.out.println(strStr(a,b));
    }


}
